/*
 * @lc app=leetcode.cn id=446 lang=typescript
 *
 * [446] 等差数列划分 II - 子序列
 */

// @lc code=start
function numberOfArithmeticSlices(nums: number[]): number {
  const m = nums.length;
  // dp[i][d]，[0,i]字串中，差值为d的序列的数量
  const dp: Map<number, number>[] = new Array(m).fill(0).map((_) => new Map());

  let ans = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < i; j++) {
      const diff = nums[i] - nums[j];
      const count = dp[j].get(diff) ?? 0;
      dp[i].set(diff, (dp[i].get(diff) ?? 0) + count + 1);
      ans += count;
    }
  }
  return ans;
}
// @lc code=end
